Modern telecommunications networks transport an enormous amount of information. Current optical networks are already capable of transporting 100 channels on a single optical fiber, where each channel can carry 40 gigabits per second. Since companies, government agencies, and the military are dependent on receiving uninterrupted service, instantaneous service restoration in the event of link or node failures has become critically important. Even service interruptions for small durations may cause significant disruptions to the exchange of information and may lead to significant financial losses and to inability of executing mission critical tasks.
The present invention focuses on optical networks where almost instantaneous restoration in the event of network failures is critically important. The prior art focuses almost exclusively on restoration under a single failure. However, such protection level may not suffice for mission critical communications. Providing dedicated restoration capacity to each of the demands would provide adequate protection, but would be prohibitively expensive. This invention designs survivable networks with guaranteed end-to-end path restoration using preconfigured cycles for a mix of demands requiring protection from one or two failures. Under normal conditions the working routes of the demands are arbitrary, often referred to as mesh routes. Once affected by a link or node failure, a demand is rerouted onto a preconfigured restoration route, using specified wavelengths, sharing restoration capacity on path protecting preconfigured cycles without resorting to intermediate switching and wavelength conversions. The term “path protection” implies path restoration of an entire working route due to a link or node failure along the working route.
A few prior solutions address restoration under dual failures using preconfigured cycles. The proposed solutions are limited to local preconfigured cycles that provide link restoration rather than end-to-end path restoration. For example, D. A. Schupke, “Multiple Failures Survivability in WDM Networks with p-Cycles”, Proceedings of the International Symposium on Circuits and Systems (ISCAS 2003), 3, 866-869, May 2003 presents analysis regarding the potential effectiveness of local preconfigured cycles designed to protect against a single failure to provide protection against dual failures. H. Wang and H. T. Mouftah, “P-Cycles in Multi-Failure Network Survivability”, Proceedings of International Conference of Transparent Optical Networks (ICTON-2005), Volume 1, 381-384, 2005 propose how to use local preconfigured cycles to address dual failures, but restoration after the second failure is not guaranteed. J. Akpuh and J. Doucette, “Enhanced Failure-Specific P-Cycle Network Dual-Failure Restorability Design and Optimization”, Journal of Optical Networking 8, 1-13, 2009 propose an integer program formulation to design local preconfigured cycles that provide dual protection.
The following articles and patent application describe methods for end-to-end path restoration under a single failure, using preconfigured cycles: A. Kodian and W. D. Grover, “Failure-Independent Path-Protecting p-Cycles: Efficient and Simple Fully Preconnected Optimal-Path Protection”, Journal of Lightwave Technology 23, 3241-3259, 2005, A. Kodian, W. D. Grover, and J. Doucette, “A Disjoint Rout-Sets Approach to Design of Path-Protecting p-Cycle Networks”, Proceedings of Workshop on Design of Reliable Communication Networks (DRCN 2005), 231-238, Naples, Italy, October 2005, and D. Baloukov, W. D. Grover, and A. Kodian, “Toward Jointly Optimized Design of Failure-Independent Path Protecting p-Cycle Networks”, Journal of Optical Networking 7, 62-79, 2008, present a survivable network design method for mesh working routes of the demands, where end-to-end restoration routes are provided on preconfigured cycles. In these prior methods, referred to as the Failure Independent Path Protecting (FIPP) p-cycles methods, multiple demands that do not have any common failure scenarios can be protected by the same cycle. However, their design method does not support the assignment of demands with common failure scenarios on the same cycle. Furthermore, their method allows splitting restoration for multiple-wavelength demands across multiple routes in the same or different cycles. M. I. Eiger, H. Luss, and D. F. Shallcross, “Network Restoration under Link or Node Failure Using Preconfigured Virtual Cycles”, U.S. patent application Ser. No. 12/388,981, filed on Feb. 19, 2009 present a survivable network design method which allows the assignment of demands with common failure scenarios on the same cycle. Their method does not allow splitting restoration for multiple-wavelength demands across multiple routes.
T. Y. Chow, F. Chudak, and A. M. Ffrench, “Fast Optical Layer Mesh Protection Using Pre-Cross-Connected Trails”, IEEE/ACM Transactions on Networking 12, 539-548, 2004, present a survivable network design method that protects mesh working routes of the demands against a single failure on restoration routes, referred to as trails, that are not constrained to be on cycles but are flexible to follow other structures such as paths with or without loops. Their method allows the sharing of restoration capacity of a trail by multiple demands that do not have any common failure scenario. Their method assigns one demand at a time, thus, constructing trails sequentially. Hence, the resulting design of trails depends on the order in which the demands are assigned. A. Grue and W. D. Grover, “Improved Method for Survivable Network Design Based on Pre-Cross-Connected Trails”, Journal of Optical Networking 6, 200-216, 2007, applied their FIPP p-cycles method to designing trails for restoration, where a trail can support only demands with no common failure scenarios and restoration routes of a demand may be split among multiple trails.
H. Luss and R. T. Wong, “Survivable Telecommunications Network Design Under Different Types of Failures”, IEEE Transactions—SMC, Part A: Systems and Humans 34, 521-530, 2004, propose a survivable network design method that provides protection from a single failure by constructing a single cycle that includes all end-nodes of the mesh routes of the demands. Restoration routes for all demands are constructed on the cycle using a pre-specified rule, such as using the shortest route on the cycle. Note that using a single cycle for restoring all demands may lead to inefficient use of capacity due to long restoration routes and the need to protect all demands on that cycle. The method is suitable primarily for logical networks (e.g., IP-MPLS); in optical networks a single restoration cycle that includes all end-nodes of the demands may not even exist. Also, the method provides only restoration routes, but does not address the issue of wavelength assignments.
The present invention designs survivable networks which provide end-to-end path protection for demands with mesh routes in the networks, using Path Protecting Preconfigured Cycles (PP-PCs), where some of the demands are protected from a single link or node failure while other demands are protected from two such failures. Restoration routes are provided on segments of cycles where the end-nodes of a working route are the end-nodes of the restoration route for the corresponding demand on the cycle. A demand protected from a single failure is assigned a single restoration route; splitting the demand among multiple restoration routes is not allowed. A demand protected from two failures is assigned two restoration routes, where again splitting the demand among multiple restoration routes is not allowed. The method allows multiple demands to share restoration capacity on a PP-PC. These demands include those with no common failure scenarios as well as selective demands that do have common failure scenarios, thus providing effective sharing of restoration capacity.